1. Field of the Invention
The present invention is generally directed to data encryption or cryptography, and more specifically, to an improved Data Encryption Standard (DES) cryptographic system for cryptographic protection of data through modifications to the cipher function and cipher key as specified in the DES.
2. Description of the Related Art
The introduction of a high grade cryptographic system to the public domain marked the commencement of serious widespread public research in the field of cryptography. The DES as promulgated by the U.S. government in FIPS PUB 46 on Jan. 15, 1977 is perhaps the most widely analyzed cryptographic system in history and has stood well against many and varied attacks. The DES has been widely employed and has served as a model for development of many other cryptographic algorithms. U.S. Pat. No. 3,962,539 issued on Jun. 8, 1976 to Ehrsam, et al. describes the basic DES device and process and is incorporated herein in its entirety by this cross reference.
The traditional DES is a block cipher, which acts on independent fixed-length, plaintext input blocks and yields fixed-length output blocks. That is, the DES encryption process maps 64-bit plaintext input blocks into 64-bit ciphertext output blocks. There are 256 (i.e. 1016.8) mappings where each mapping selected by a 56-bit keying variable is unique and invertible. The DES decryption is a reverse of the encryption mapping, and requires knowledge of the specific keying variable used in the encryption process.
The use of the DES as a cryptographic system is built around its most basic mode, which is known as the Electronic Code Book (ECB) mode. Other modes of DES, such as Cipher Block Chaining (CBC), Cipher Feedback (CFB) and Output Feedback (OFB), are described in the Federal Information Processing Standards Publication (FIPS PUB) number 81. In the ECB mode, a 64-bit plaintext word is converted to a 64-bit ciphertext word. This conversion is a one-to one and reverse mapping is electable. This conversion is also done under the control of a 56-bit keying variable. The keying variable for the DES is generally given as 64-bits with the convention of using 8 bits as the odd parity bits.
Alternative Modes of Using the DES from FIPS PUB 81, DES Modes of Operation are the Cipher Block Chaining (CBC) mode, the Cipher Feedback (CFB) mode, and the Output Feedback (OFB) mode. ECB is a direct application of the DES algorithm to encrypt and decrypt data; CBC is an enhanced mode of ECB which chains together blocks of cipher text; CFB uses previously generated cipher text as input to the DES to generate pseudorandom outputs which are combined with the plaintext to produce cipher, thereby chaining together the resulting cipher; OFB is identical to CFB except that the previous output of the DES is used as input in OFB while the previous cipher is used as input in CFB. OFB does not chain the cipher.
With the inexorable advance in available worldwide computer power coupled with the existing fame of the DES algorithm, it was inevitable that the DES algorithm would continue to draw attention and challenges as to its sufficiency in protecting data at the highest level. In particular, challenges have been mounted through parallel exhaustive attack and so-called special attacks in which one seeks to find a path to a solution that is computationally less than that of simple exhaustion.
There are two important publications with respect to cryptanalysis of the DES cryptoprinciple. The publications represent two very powerful distinct cryptanalytic approaches. Neither approach was initially successful at defeating the DES but both approaches deserve consideration as genres of potent cryptanalysis. The first of these was reported in the paper “Exhaustive Cryptanalysis of the NBS Data Encryption Standard” by W. Diffie and M. Hellman (Computer June 12977, pp. 74–84). This paper discussed the construction of a large parallel processor in which the entire 56-bit keying variable space was partitioned over a very large number of identical independent processors. The paper also advanced the argument that declining computation costs would eventually reduce the cost of a solution to a nominal sum.
This type of attack can be countered, of course, by increasing the size of the keying variable and it would not require a variable of much larger size than the 56-bit variable to effectively frustrate this approach.
The second attack is detailed in a lengthy paper entitled “Differential Cryptanalysis of DES-like Cryptosystem” by E. Biham and A. Shamir (The Weizmann Institute of Science/Department of Applied Mathematics, Jun. 18, 1990). This paper is a seminal work in academic cryptography. It introduces a new statistical cryptanalytic method termed Differential Cryptanalysis that the authors described as “a method which analyses the effect of particular differences in plaintext pairs on the differences of the resultant ciphertext pairs.” These differences can be used to assign probabilities to the possible keys and to locate the most probable key.
Biham and Shamir use the DES as an example for their new cryptanalytic method. They characterize the DES as an iterated crypto system in that it realizes a strong cryptographic function by iterating a weaker function many times. Their attack is based on Boolean differencing in which the structure of the DES appears to be an ideal candidate for this type of cryptanalysis.
When applied to the DES, their attack would have beaten exhaustion if the DES had used less than 16 rounds of iteration. In particular, the following points were observed:                (1) modification of the key scheduling algorithm cannot make the DES much stronger;        (2) the attacks on DES with 9–16 rounds are not influenced by the P permutation and the replacement of the P permutation by any other fixed permutation or function cannot make them less successful;        (3) replacement of the order of the S-boxes without changing their values can make the DES weaker;        (4) replacement of the XOR operation by the more complex addition operation makes the DES much weaker; and        (5) the DES with randomly chosen S-boxes is very easy to break. Even a change of one entry in one S-box can make the DES easier to break.        
The initial differentiation cryptanalytic technique was shown successful against a DES with fewer than 16 rounds because the statistical characteristics of the Boolean function combining can be easily discovered and tests built around these statistics.
Further work related to differential cryptanalysis encompasses so called linear cryptanalysis (“Linear Cryptanalysis Method for DES Cipher,” Mistura Matsui, Abstracts of EUROCRYPT'93, pp. W112–123) and statistical attacks by Davis and others. Biham and Shamir published an improvement of one of these attacks in “An Improvement of Davies' Attack on DES,” EUROCRYPT '94, pp. 461–467. In this paper they reported breaking the full 16-round DES faster than exhaustive search. The statistical attack requires a larger volume of known plaintext-ciphertext pairs.
What the various cryptographic attacks and the increase in computer power available to exhaust (i.e. try all possible ) the 56 bit key of single DES have done is cause the U.S. Government to recommend using TDEA or Triple DES. TDEA basically uses the 16 rounds of the single DES engine three times with different cryptographic keys to provide increased security. The penalty that is paid for the TDEA is a three fold increase in running time over the single DES.
As noted in FIPS PUB 46-3 Oct. 25, 1999: “With regard to the use of single DES, exhaustion of the DES (i.e. breaking a DES encrypted ciphertext by trying all possible keys) has become increasingly more feasible with technology advances. Following a recent hardware based DES key exhaustion attack, NIST can no longer support the use of single DES for many applications. Therefore, Government agencies with legacy systems are encouraged to transition to Triple DES. Agencies are advised to implement Triple DES when building new systems.”
Also from FIPS PUB 46-3: “DES forms the basis for TDEA (Triple Data Encryption Algorithm or Triple DES).” “The X9.52 standard, “Triple Data Encryption Algorithm Modes of Operation” describes seven different modes for using TDEA (Triple Data Encryption Algorithm or Triple DES) described in this standard. These seven modes are called the TDEA Electronic Codebook Mode of Operation (TECB) mode, the TDEA Cipher Block Chaining Mode of Operation (TCBC), the TDEA Cipher Block Chaining Mode of Operation—Interleaved (TCBC-I), the TDEA Cipher Feedback Mode of Operation (TCFB), the TDEA Cipher Feedback Mode of Operation—Pipelined (TCFB-P), the TDEA Output Feedback Mode of Operation (TOFB), and the TDEA Output Feedback Mode of Operation—Interleaved (TOFB-I). The TECB, TCBC, TCFB and TOFB modes are based upon the ECB, CBC, CFB and OFB modes respectively obtained by substituting the DES encryption/decryption operation with the TDEA encryption/decryption operation.
A DES key consists of 64 binary digits (“0”s or “1”s) of which 56 bits are randomly generated and used directly by the algorithm. The other 8 bits, which are not used by the algorithm, may be used for error detection. The 8 error detection bits are set to make the parity of each 8-bit byte of the key odd, i.e., there is an odd number of “1 ”s in each 8-bit byte. A TDEA key consists of three DES keys, which is also referred to as a key bundle. Authorized users of encrypted computer data must have the key that was used to encipher the data in order to decrypt it. The encryption algorithms specified in this standard (i.e. FIPS 46-3) are commonly known among those using the standard.
This standard became effective July 1977. It was reaffirmed in 1983, 1988, 1993, and 1999. It applies to all Federal agencies, contractors of Federal agencies, or other organizations that process information (using a computer or telecommunications system) on behalf of the Federal Government to accomplish a Federal function. Each Federal agency or department may issue internal directives for the use of this standard by their operating units based on their data security requirement determinations.
With this modification of the FIPS 46-2 standard (i.e. FIPS 46-3):    1. Triple DES (i.e., TDEA), as specified in ANSI X9.52 will be recognized as a FIPS approved algorithm.    2. Triple DES will be the FIPS approved symmetric encryption algorithm of choice.    3. Single DES (i.e DES) will be permitted for legacy systems only. New procurements to support legacy systems should, where feasible, use Triple DES products running in the single DES configuration.